package com.leo.offer;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序数组的一个旋转，输出旋转数组的最小元素。
 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1
 * @author xuexiaolei
 * @version 2018年03月01日
 */
public class T08 {
    public static int finMin(int[] a){
        if (a == null) { return 0; }
        if (a.length == 1) { return a[0]; }

        int i = 0,j = a.length-1,mid=0;
        while (a[i] >= a[j]){
            if (i == j-1){
                mid = j;
                break;
            }
            mid = (i+j) / 2;
            //考虑两侧数字和中间数字相同的特殊情况，采用顺序查找算法查找最小值
            if (a[i] == a[mid] && a[mid]==a[j]){
                int res = a[i];
                for (int k = i; k <=j ; k++) {
                    if (a[k] < res) { res = a[k]; }
                }
                return res;
            }
            if (a[mid] >= a[i]) {
                i=mid;
            }else {
                j=mid;
            }
        }
        return a[mid];
    }

    public static void main(String[] args) {
        System.out.println(finMin(new int[]{3,4,5,1,2}));
        System.out.println(finMin(new int[]{2,1}));
        System.out.println(finMin(new int[]{2,4,2,2,2,2,2}));
        System.out.println(finMin(new int[]{2,4,5,6,7,8,2,2,2,2,2}));
    }
}
